//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,2,2,1]
//输出：true
// 
//
// 示例 2： 
// 
// 
//输入：head = [1,2]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目在范围[1, 10⁵] 内 
// 0 <= Node.val <= 9 
// 
//
// 
//
// 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
//
// Related Topics 栈 递归 链表 双指针 👍 1752 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-08-14 01:06:29
 * @description 234.回文链表
 */
public class PalindromeLinkedList{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new PalindromeLinkedList().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
 class ListNode {
	int val;
	ListNode next;
	ListNode() {}
	ListNode(int val) { this.val = val; }
	ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
		 /*笨办法1，放入数组，笨办法2，翻转后遍历，时间空间O（n)*/
	/*方法一，递归时间空间O（n)，用内外指针去比较*/
		 private ListNode outP;
    public boolean isPalindrome(ListNode head) {
		outP=head;
		return check(head);
    }
	private boolean check(ListNode inP){
		//遍历完
		if(inP!=null){
			//
			if (!check(inP.next)){
				return false;
			}
			if(inP.val!= outP.val){
				return false;
			}
			outP=outP.next;
		}
		return true;
	}

	/*方法二快慢指针
	* 找到前半部分链表的尾节点。
	反转后半部分链表。
	判断是否回文。
	恢复链表。
	返回结果。*/
	public boolean isPalindrome1(ListNode head) {
		if (head == null) {
			return true;
		}
		/*找到前半部分链表的尾节点。
		反转后半部分链表。*/
		ListNode firstHalfEnd = endOfFirstHalf(head);
		ListNode secondHalfStart = reverseList(firstHalfEnd.next);
		//判断回文
		ListNode p1=head;
		ListNode p2=secondHalfStart;
		boolean flag=true;
		while (p2!=null){
			if(p1.val!=p2.val){
				flag=false;
				break;
			}
			p1=p1.next;
			p2=p2.next;
		}
		//还原后半部分
		firstHalfEnd.next = reverseList(secondHalfStart);
		return flag;

	}
	//反转链表
	private ListNode reverseList(ListNode head) {
		ListNode pre=null;
		ListNode curr=head;
		while (curr!=null){
			ListNode next = curr.next;
			curr.next=pre;
			pre=curr;
			curr=next;
		}
		return pre;
	}
	//寻找中点
	private ListNode endOfFirstHalf(ListNode head) {
		ListNode fast = head;
		ListNode slow = head;
		while (fast.next != null && fast.next.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}
		return slow;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
